SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Block code</title>

</head>

Block code

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, block codes are a large and important family of <a href="Channel_coding" class="mw-redirect" title="Channel coding">error-correcting codes</a> that encode data in blocks.

There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, <a href="Mathematician" title="Mathematician">mathematicians</a>, and <a href="Computer_scientist" title="Computer scientist">computer scientists</a> to study the limitations of all block codes in a unified way.

Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.

Examples of block codes are <a href="Reed%E2%80%93Solomon_code" class="mw-redirect" title="Reed–Solomon code">Reed–Solomon codes</a>, <a href="Hamming_code" title="Hamming code">Hamming codes</a>, <a href="Hadamard_code" title="Hadamard code">Hadamard codes</a>, <a href="Expander_code" title="Expander code">Expander codes</a>, <a href="Golay_code_(disambiguation)" class="mw-redirect mw-disambig" title="Golay code (disambiguation)">Golay codes</a>, <a href="Reed%E2%80%93Muller_code" title="Reed–Muller code">Reed–Muller codes</a> and <a href="Polar_code_(coding_theory)" title="Polar code (coding theory)">Polar codes</a>. These examples also belong to the class of <a href="Linear_code" title="Linear code">linear codes</a>, and hence they are called linear block codes. More particularly, these codes are known as algebraic block codes, or cyclic block codes, because they can be generated using Boolean polynomials.

Algebraic block codes are typically <a href="Soft-decision_decoder" title="Soft-decision decoder">hard-decoded</a> using algebraic decoders.

The term block code may also refer to any error-correcting code that acts on a block of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> bits of input data to produce <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> bits of output data <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k)}</annotation>

</semantics>

</math><img src="./47f4659640cd0bb3ab77e4d61a81328ca4dd8a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.449ex; height:2.843ex;" alt="{\displaystyle (n,k)}" loading="lazy">. Consequently, the block coder is a memoryless device. Under this definition codes such as <a href="Turbo_code" title="Turbo code">turbo codes</a>, terminated convolutional codes and other iteratively decodable codes (turbo-like codes) would also be considered block codes. A non-terminated convolutional encoder would be an example of a non-block (unframed) code, which has memory and is instead classified as a tree code.

This article deals with "algebraic block codes".

<div class="mw-heading mw-heading2"><h2 id="The_block_code_and_its_parameters">The block code and its parameters</h2></div>

<a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">Error-correcting codes</a> are used to <a href="Reliability_(computer_networking)" title="Reliability (computer networking)">reliably</a> transmit <a href="Digital_data" title="Digital data">digital data</a> over unreliable <a href="Communication_channel" title="Communication channel">communication channels</a> subject to <a href="Channel_noise" class="mw-redirect" title="Channel noise">channel noise</a>.

When a sender wants to transmit a possibly very long data stream using a block code, the sender breaks the stream up into pieces of some fixed size. Each such piece is called message and the procedure given by the block code encodes each message individually into a codeword, also called a block in the context of block codes. The sender then transmits all blocks to the receiver, who can in turn use some decoding mechanism to (hopefully) recover the original messages from the possibly corrupted received blocks.

The performance and success of the overall transmission depends on the parameters of the channel and the block code.

Formally, a block code is an <a href="Injective" class="mw-redirect" title="Injective">injective</a> mapping

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C:\Sigma ^{k}\to \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./fbb0bbe598f5167b665b49b70cf3cc255d7df534.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.981ex; height:2.676ex;" alt="{\displaystyle C:\Sigma ^{k}\to \Sigma ^{n}}" loading="lazy">.</dd></dl>

Here, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> is a finite and nonempty <a href="Set_(mathematics)" title="Set (mathematics)">set</a> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> are integers. The meaning and significance of these three parameters and other parameters related to the code are described below.

<div class="mw-heading mw-heading3"><h3 id="The_alphabet_Σ">The alphabet Σ</h3></div>

The data stream to be encoded is modeled as a <a href="String_(computer_science)" title="String (computer science)">string</a> over some alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy">. The size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Sigma |}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Sigma |}</annotation>

</semantics>

</math><img src="./a3144c4ed2f2928cbe0c88cf96d3806bde792038.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle |\Sigma |}" loading="lazy"> of the alphabet is often written as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=2}</annotation>

</semantics>

</math><img src="./26622af6012fb982cab4e9584f57dd4f364233b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q=2}" loading="lazy">, then the block code is called a binary block code. In many applications it is useful to consider <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> to be a <a href="Prime_power" title="Prime power">prime power</a>, and to identify <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> with the <a href="Finite_field" title="Finite field">finite field</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}}</annotation>

</semantics>

</math><img src="./dbb96e056c071d13fc7702013f9273e7f5cd88a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.409ex; height:2.843ex;" alt="{\displaystyle \mathbb {F} _{q}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="The_message_length_k">The message length k</h3></div>

Messages are elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{k}}</annotation>

</semantics>

</math><img src="./cd5c5bcf918e3bae51f28e82161513e60cdabbd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.767ex; height:2.676ex;" alt="{\displaystyle \Sigma ^{k}}" loading="lazy">, that is, strings of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">.

Hence the number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is called the message length or dimension of a block code.

<div class="mw-heading mw-heading3"><h3 id="The_block_length_n">The block length n</h3></div>

The block length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> of a block code is the number of symbols in a block. Hence, the elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./e52398b6b9103472077e244c7db84eaeab4accdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{n}}" loading="lazy"> are strings of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and correspond to blocks that may be received by the receiver. Hence they are also called received words.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=C(m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=C(m)}</annotation>

</semantics>

</math><img src="./9501579a2c037598f1a513252d282131a1e66e8a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.721ex; height:2.843ex;" alt="{\displaystyle c=C(m)}" loading="lazy"> for some message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> is called the codeword of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">.

The rate of a block code is defined as the ratio between its message length and its block length:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R=k/n}</annotation>

</semantics>

</math><img src="./413a3d4d51a7ee9b5b884497ab1dda55a18d0e99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.631ex; height:2.843ex;" alt="{\displaystyle R=k/n}" loading="lazy">.</dd></dl>

A large rate means that the amount of actual message per transmitted block is high. In this sense, the rate measures the transmission speed and the quantity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-R}</annotation>

</semantics>

</math><img src="./9ef50c0caa439f406160ed56f46690ed0f528310.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.767ex; height:2.343ex;" alt="{\displaystyle 1-R}" loading="lazy"> measures the overhead that occurs due to the encoding with the block code.

It is a simple <a href="Information_theory" title="Information theory">information theoretical</a> fact that the rate cannot exceed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> since data cannot in general be losslessly compressed. Formally, this follows from the fact that the code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is an injective map.

<div class="mw-heading mw-heading3"><h3 id="The_distance_d">The distance d</h3></div>

The distance or minimum distance d of a block code is the minimum number of positions in which any two distinct codewords differ, and the relative distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"> is the fraction <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d/n}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d/n}</annotation>

</semantics>

</math><img src="./593b57025807fc1742d6a097080c1851b3073a50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.773ex; height:2.843ex;" alt="{\displaystyle d/n}" loading="lazy">.

Formally, for received words <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{1},c_{2}\in \Sigma ^{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1},c_{2}\in \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./26111896462912cd431676b170a6dba9f9e4ce08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.893ex; height:2.676ex;" alt="{\displaystyle c_{1},c_{2}\in \Sigma ^{n}}" loading="lazy">, let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (c_{1},c_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (c_{1},c_{2})}</annotation>

</semantics>

</math><img src="./18f5e7ae10a6c3a3051e0561e94628dc227712f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.901ex; height:2.843ex;" alt="{\displaystyle \Delta (c_{1},c_{2})}" loading="lazy"> denote the <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1}}</annotation>

</semantics>

</math><img src="./77b7dc6d279091d354e0b90889b463bfa7eb7247.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{2}}</annotation>

</semantics>

</math><img src="./0b30ba1b247fb8d334580cec68561e749d24aff2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{2}}" loading="lazy">, that is, the number of positions in which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1}}</annotation>

</semantics>

</math><img src="./77b7dc6d279091d354e0b90889b463bfa7eb7247.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{2}}</annotation>

</semantics>

</math><img src="./0b30ba1b247fb8d334580cec68561e749d24aff2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{2}}" loading="lazy"> differ.

Then the minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> of the code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is defined as

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}</annotation>

</semantics>

</math><img src="./e18b5dbaf37ec5d007e818f498c3da826bf19767.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:30.507ex; height:6.509ex;" alt="{\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}" loading="lazy">.</dd></dl>

Since any code has to be <a href="Injective" class="mw-redirect" title="Injective">injective</a>, any two codewords will disagree in at least one position, so the distance of any code is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">. Besides, the distance equals the <a href="Hamming_weight#Minimum_weight" title="Hamming weight">minimum weight</a> for linear block codes because:

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{2})-C(m_{1})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}</annotation>

</semantics>

</math><img src="./e68e8f750ec4be3b12550efbe5a5c96469d5681f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:82.572ex; height:6.509ex;" alt="{\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{2})-C(m_{1})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}" loading="lazy">.</dd></dl>

A larger distance allows for more error correction and detection.

For example, if we only consider errors that may change symbols of the sent codeword but never erase or add them, then the number of errors is the number of positions in which the sent codeword and the received word differ.

A code with distance d allows the receiver to detect up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy"> transmission errors since changing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy"> positions of a codeword can never accidentally yield another codeword. Furthermore, if no more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (d-1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (d-1)/2}</annotation>

</semantics>

</math><img src="./67305c3b9f46943113c85c4c3e85885720bfcf6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.353ex; height:2.843ex;" alt="{\displaystyle (d-1)/2}" loading="lazy"> transmission errors occur, the receiver can uniquely decode the received word to a codeword. This is because every received word has at most one codeword at distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (d-1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (d-1)/2}</annotation>

</semantics>

</math><img src="./67305c3b9f46943113c85c4c3e85885720bfcf6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.353ex; height:2.843ex;" alt="{\displaystyle (d-1)/2}" loading="lazy">. If more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (d-1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (d-1)/2}</annotation>

</semantics>

</math><img src="./67305c3b9f46943113c85c4c3e85885720bfcf6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.353ex; height:2.843ex;" alt="{\displaystyle (d-1)/2}" loading="lazy"> transmission errors occur, the receiver cannot uniquely decode the received word in general as there might be several possible codewords. One way for the receiver to cope with this situation is to use <a href="List_decoding" title="List decoding">list decoding</a>, in which the decoder outputs a list of all codewords in a certain radius.

<div class="mw-heading mw-heading3"><h3 id="Popular_notation">Popular notation</h3></div>

The notation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,k,d)_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k,d)_{q}}</annotation>

</semantics>

</math><img src="./cbff03b80f1c9a5ce9a3ea783f4dc10b86f78aaa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.688ex; height:3.009ex;" alt="{\displaystyle (n,k,d)_{q}}" loading="lazy"> describes a block code over an alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">, with a block length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, message length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, and distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">.

If the block code is a linear block code, then the square brackets in the notation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k,d]_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k,d]_{q}}</annotation>

</semantics>

</math><img src="./5eef76e1d6b74cc535236a6249e75afeea540ee3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.172ex; height:3.009ex;" alt="{\displaystyle [n,k,d]_{q}}" loading="lazy"> are used to represent that fact.

For binary codes with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=2}</annotation>

</semantics>

</math><img src="./26622af6012fb982cab4e9584f57dd4f364233b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q=2}" loading="lazy">, the index is sometimes dropped.

For <a href="Maximum_distance_separable_code" class="mw-redirect" title="Maximum distance separable code">maximum distance separable codes</a>, the distance is always <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=n-k+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=n-k+1}</annotation>

</semantics>

</math><img src="./0990fa9c410b95fed78e55519575a44021a19f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.764ex; height:2.343ex;" alt="{\displaystyle d=n-k+1}" loading="lazy">, but sometimes the precise distance is not known, non-trivial to prove or state, or not needed. In such cases, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">-component may be missing.

Sometimes, especially for non-block codes, the notation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,M,d)_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,M,d)_{q}}</annotation>

</semantics>

</math><img src="./e1b46da569879ef67eb1b3e8950ae53224e15a19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.919ex; height:3.009ex;" alt="{\displaystyle (n,M,d)_{q}}" loading="lazy"> is used for codes that contain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> codewords of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. For block codes with messages of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> over an alphabet of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">, this number would be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M=q^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M=q^{k}}</annotation>

</semantics>

</math><img src="./bfb03e47c2e79061541c76901df1a02fcfd6d869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.709ex; height:3.009ex;" alt="{\displaystyle M=q^{k}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

As mentioned above, there are a vast number of error-correcting codes that are actually block codes.

The first error-correcting code was the <a href="Hamming(7%2C4)" title="Hamming(7,4)">Hamming(7,4)</a> code, developed by <a href="Richard_W._Hamming" class="mw-redirect" title="Richard W. Hamming">Richard W. Hamming</a> in 1950. This code transforms a message consisting of 4 bits into a codeword of 7 bits by adding 3 parity bits. Hence this code is a block code. It turns out that it is also a linear code and that it has distance 3. In the shorthand notation above, this means that the Hamming(7,4) code is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [7,4,3]_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [7,4,3]_{2}}</annotation>

</semantics>

</math><img src="./499457f6464e18a49d7e72d66681299c4862829a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.903ex; height:2.843ex;" alt="{\displaystyle [7,4,3]_{2}}" loading="lazy"> code.

<a href="Reed%E2%80%93Solomon_code" class="mw-redirect" title="Reed–Solomon code">Reed–Solomon codes</a> are a family of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k,d]_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k,d]_{q}}</annotation>

</semantics>

</math><img src="./5eef76e1d6b74cc535236a6249e75afeea540ee3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.172ex; height:3.009ex;" alt="{\displaystyle [n,k,d]_{q}}" loading="lazy"> codes with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=n-k+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=n-k+1}</annotation>

</semantics>

</math><img src="./0990fa9c410b95fed78e55519575a44021a19f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.764ex; height:2.343ex;" alt="{\displaystyle d=n-k+1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> being a <a href="Prime_power" title="Prime power">prime power</a>. <a href="Rank_error-correcting_code" title="Rank error-correcting code">Rank codes</a> are family of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k,d]_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k,d]_{q}}</annotation>

</semantics>

</math><img src="./5eef76e1d6b74cc535236a6249e75afeea540ee3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.172ex; height:3.009ex;" alt="{\displaystyle [n,k,d]_{q}}" loading="lazy"> codes with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\leq n-k+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\leq n-k+1}</annotation>

</semantics>

</math><img src="./d554ddcf246d03db4f7cbe0f80ac3e9111037549.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.764ex; height:2.343ex;" alt="{\displaystyle d\leq n-k+1}" loading="lazy">. <a href="Hadamard_code" title="Hadamard code">Hadamard codes</a> are a family of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k,d]_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k,d]_{2}}</annotation>

</semantics>

</math><img src="./6392bca52bc90f88c7d4362f078cf66ff24fb557.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.238ex; height:2.843ex;" alt="{\displaystyle [n,k,d]_{2}}" loading="lazy"> codes with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{k-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{k-1}}</annotation>

</semantics>

</math><img src="./f4b460a6fe1b4da0a15c0d2403e974d6541efaf9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.845ex; height:2.676ex;" alt="{\displaystyle n=2^{k-1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=2^{k-2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=2^{k-2}}</annotation>

</semantics>

</math><img src="./4d112bf05d5778a2d9a23aca59fe7b98b3f3d1ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.666ex; height:2.676ex;" alt="{\displaystyle d=2^{k-2}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Error_detection_and_correction_properties">Error detection and correction properties</h2></div>

A codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./6a60d46b6ec4b419f603ac75aa0416ebce660891.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.744ex; height:2.343ex;" alt="{\displaystyle c\in \Sigma ^{n}}" loading="lazy">could be considered as a point in the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-dimension space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./e52398b6b9103472077e244c7db84eaeab4accdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{n}}" loading="lazy"> and the code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> is the subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./e52398b6b9103472077e244c7db84eaeab4accdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{n}}" loading="lazy">. A code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> has distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall c\in {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall c\in {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./ea667d1ee4a2818a86f396f4ca949402d1f15086.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.379ex; height:2.176ex;" alt="{\displaystyle \forall c\in {\mathcal {C}}}" loading="lazy">, there is no other codeword in the <a href="Hamming_ball" title="Hamming ball">Hamming ball</a> centered at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> with radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy">, which is defined as the collection of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-dimension words whose <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> is no more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy">. Similarly, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> with (minimum) distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> has the following properties:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> can detect <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy"> errors : Because a codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> is the only codeword in the Hamming ball centered at itself with radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy">, no error pattern of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy"> or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy">, the errors are detected (but no guarantee to correct).</li>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> can correct <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }">

<mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }</annotation>

</semantics>

</math><img src="./d4d2235bb32b05670a3621af3868d59562156e18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.251ex; height:4.843ex;" alt="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }" loading="lazy"> errors. Because a codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> is the only codeword in the Hamming ball centered at itself with radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy">, the two Hamming balls centered at two different codewords respectively with both radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }">

<mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }</annotation>

</semantics>

</math><img src="./d4d2235bb32b05670a3621af3868d59562156e18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.251ex; height:4.843ex;" alt="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }" loading="lazy"> do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">, as long as the number of errors is no more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }">

<mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }</annotation>

</semantics>

</math><img src="./d4d2235bb32b05670a3621af3868d59562156e18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.251ex; height:4.843ex;" alt="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }" loading="lazy">, there is only one codeword in the hamming ball centered at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> with radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }">

<mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }</annotation>

</semantics>

</math><img src="./d4d2235bb32b05670a3621af3868d59562156e18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.251ex; height:4.843ex;" alt="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }" loading="lazy">, therefore all errors could be corrected.</li>

<li>In order to decode in the presence of more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (d-1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (d-1)/2}</annotation>

</semantics>

</math><img src="./67305c3b9f46943113c85c4c3e85885720bfcf6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.353ex; height:2.843ex;" alt="{\displaystyle (d-1)/2}" loading="lazy"> errors, <a href="List-decoding" class="mw-redirect" title="List-decoding">list-decoding</a> or <a href="Decoding_methods#Maximum_likelihood_decoding" title="Decoding methods">maximum likelihood decoding</a> can be used.</li>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> can correct <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d-1}</annotation>

</semantics>

</math><img src="./0195b64ba44bcc80b4c98e9d34256b4043fe519e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d-1}" loading="lazy"> <a href="Binary_erasure_channel" title="Binary erasure channel">erasures</a>. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">-passing decoding : In <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> passing the erased position is filled with the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> symbol and error correcting is carried out. There must be one passing that the number of errors is no more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }">

<mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }</annotation>

</semantics>

</math><img src="./d4d2235bb32b05670a3621af3868d59562156e18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.251ex; height:4.843ex;" alt="{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }" loading="lazy"> and therefore the erasures could be corrected.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Lower_and_upper_bounds_of_block_codes">Lower and upper bounds of block codes</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Family_of_codes">Family of codes</h3></div>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=\{C_{i}\}_{i\geq 1}}</annotation>

</semantics>

</math><img src="./eaa922b85ced1609a5f64a30f47a2d4e4456574c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.551ex; height:2.843ex;" alt="{\displaystyle C=\{C_{i}\}_{i\geq 1}}" loading="lazy"> is called family of codes, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"> is an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n_{i},k_{i},d_{i})_{q}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n_{i},k_{i},d_{i})_{q}}</annotation>

</semantics>

</math><img src="./b963772569559743a171083eb6f6513352125545.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.08ex; height:3.009ex;" alt="{\displaystyle (n_{i},k_{i},d_{i})_{q}}" loading="lazy"> code with monotonic increasing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{i}}</annotation>

</semantics>

</math><img src="./57f87f905ba5a4d8c691ccaecd65fc47bd007ba4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.194ex; height:2.009ex;" alt="{\displaystyle n_{i}}" loading="lazy">.

Rate of family of codes C is defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}">

</mrow>

</munder>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}</annotation>

</semantics>

</math><img src="./dc567409092442b4a262b2cf0527b56c7161da48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:15.709ex; height:5.676ex;" alt="{\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}" loading="lazy">

Relative distance of family of codes C is defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}">

</mrow>

</munder>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}</annotation>

</semantics>

</math><img src="./15062fb876c2509926e9f42afab86f14393c9658.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:14.994ex; height:5.676ex;" alt="{\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}" loading="lazy">

To explore the relationship between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(C)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(C)}</annotation>

</semantics>

</math><img src="./e4a8ce2da3180bf4e0d0dd0701679fa28c2027c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.34ex; height:2.843ex;" alt="{\displaystyle R(C)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (C)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (C)}</annotation>

</semantics>

</math><img src="./76973f4d905f13544544255a441e0c202ff03670.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.624ex; height:2.843ex;" alt="{\displaystyle \delta (C)}" loading="lazy">, a set of lower and upper bounds of block codes are known.

<div class="mw-heading mw-heading3"><h3 id="Hamming_bound">Hamming bound</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Hamming_bound" title="Hamming bound">Hamming bound</a></div>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

<mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}</annotation>

</semantics>

</math><img src="./7fcd5bd29f60ab24152148b90b87025547204969.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.838ex; width:40.193ex; height:10.843ex;" alt="{\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Singleton_bound">Singleton bound</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Singleton_bound" title="Singleton bound">Singleton bound</a></div>

The Singleton bound is that the sum of the rate and the relative distance of a block code cannot be much larger than 1:

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R+\delta \leq 1+{\frac {1}{n}}}</annotation>

</semantics>

</math><img src="./d3205f8eb5c156b36b1ca43181a8bd3cd751e296.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:14.985ex; height:5.176ex;" alt="{\displaystyle R+\delta \leq 1+{\frac {1}{n}}}" loading="lazy">.</dd></dl>

In other words, every block code satisfies the inequality <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k+d\leq n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k+d\leq n+1}</annotation>

</semantics>

</math><img src="./39463061e873b658c8e124e85e178fadbdb850ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.764ex; height:2.343ex;" alt="{\displaystyle k+d\leq n+1}" loading="lazy">.

<a href="Reed%E2%80%93Solomon_code" class="mw-redirect" title="Reed–Solomon code">Reed–Solomon codes</a> are non-trivial examples of codes that satisfy the singleton bound with equality.

<div class="mw-heading mw-heading3"><h3 id="Plotkin_bound">Plotkin bound</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Plotkin_bound" title="Plotkin bound">Plotkin bound</a></div>

For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=2}</annotation>

</semantics>

</math><img src="./26622af6012fb982cab4e9584f57dd4f364233b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q=2}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R+2\delta \leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R+2\delta \leq 1}</annotation>

</semantics>

</math><img src="./441c069e1b3e89b031482963f9ff9c391b1212c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.076ex; height:2.509ex;" alt="{\displaystyle R+2\delta \leq 1}" loading="lazy">. In other words, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k+2d\leq n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k+2d\leq n}</annotation>

</semantics>

</math><img src="./825ac88f6a4f5cc896d245c3cb99824f46e09c1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.923ex; height:2.343ex;" alt="{\displaystyle k+2d\leq n}" loading="lazy">.

For the general case, the following Plotkin bounds holds for any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./91debd30a913516e0d6e5d0eec87ee0b467e2086.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.504ex; height:3.176ex;" alt="{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}" loading="lazy"> with distance d:

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}</annotation>

</semantics>

</math><img src="./378ca3f62762aa280a59a7e4d4d913b524f08b96.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:26.338ex; height:6.176ex;" alt="{\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}" loading="lazy"></li>

<li>If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}</annotation>

</semantics>

</math><img src="./2c7f86db97e98cad2b6e5401d8cebaa8721477d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:37.337ex; height:6.343ex;" alt="{\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}" loading="lazy"></li></ol>

For any q-ary code with distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}">

<mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}</annotation>

</semantics>

</math><img src="./6b5a2f78174db3715afc4c416f9e10b2c9e7c08f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:26.958ex; height:6.176ex;" alt="{\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Gilbert–Varshamov_bound">Gilbert–Varshamov bound</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Gilbert%E2%80%93Varshamov_bound" title="Gilbert–Varshamov bound">Gilbert–Varshamov bound</a></div>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }</annotation>

</semantics>

</math><img src="./321b8d408f03f9ca1a8bdfe8fe4f0beea3bf321f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.815ex; height:3.009ex;" alt="{\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}">

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}</annotation>

</semantics>

</math><img src="./020117bd3fb6e71c3abd1db133a55dbe3bd86972.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:33.915ex; height:5.676ex;" alt="{\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}" loading="lazy">,

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mover>

</mrow>

</munder>

</mover>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

</mrow>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}</annotation>

</semantics>

</math><img src="./667e8a5299ed6b96b030a7465a0847e464efdd6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:49.081ex; height:5.343ex;" alt="{\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}" loading="lazy"> is the q-ary entropy function.

<div class="mw-heading mw-heading3"><h3 id="Johnson_bound">Johnson bound</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Johnson_bound" title="Johnson bound">Johnson bound</a></div>

Define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}">

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mover>

</mrow>

</munder>

</mover>

</mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mrow>

<msqrt>

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}</annotation>

</semantics>

</math><img src="./b11512e7d7c0360489f1e9bbbd74fb82cee299ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:39.02ex; height:7.676ex;" alt="{\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}" loading="lazy">.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J_{q}\left(n,d,e\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J_{q}\left(n,d,e\right)}</annotation>

</semantics>

</math><img src="./10f6f080d5613f1c3db7ca65e9b2ca8bd58012eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.237ex; height:3.009ex;" alt="{\displaystyle J_{q}\left(n,d,e\right)}" loading="lazy"> be the maximum number of codewords in a Hamming ball of radius e for any code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./91debd30a913516e0d6e5d0eec87ee0b467e2086.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.504ex; height:3.176ex;" alt="{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}" loading="lazy"> of distance d.

Then we have the Johnson Bound : <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J_{q}\left(n,d,e\right)\leq qnd}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J_{q}\left(n,d,e\right)\leq qnd}</annotation>

</semantics>

</math><img src="./f81a2427e0f51a6916957521f3cdafd665d93a22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.016ex; height:3.009ex;" alt="{\displaystyle J_{q}\left(n,d,e\right)\leq qnd}" loading="lazy">, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}">

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mrow>

</mfrac>

</mrow>

<mrow>

<mrow>

<msqrt>

<mfrac>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msqrt>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}</annotation>

</semantics>

</math><img src="./d510d605a85ed5e18ea80cf736b77160f3a47120.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:47.258ex; height:7.509ex;" alt="{\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Elias–Bassalygo_bound">Elias–Bassalygo bound</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Elias_Bassalygo_bound" title="Elias Bassalygo bound">Elias Bassalygo bound</a></div>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}</annotation>

</semantics>

</math><img src="./6c386d47fe64761821e71f9b89c544b6ccf1c5cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:38.174ex; height:6.009ex;" alt="{\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Sphere_packings_and_lattices">Sphere packings and lattices</h2></div>

Block codes are tied to the <a href="Sphere_packing_problem" class="mw-redirect" title="Sphere packing problem">sphere packing problem</a> which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful <a href="Binary_Golay_code" title="Binary Golay code">Golay code</a> used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is), the dimensions refer to the length of the codeword as defined above.

The theory of coding uses the N-dimensional sphere model. For example, how many pennies can be packed into a circle on a tabletop or in 3 dimensions, how many marbles can be packed into a globe. Other considerations enter the choice of a code. For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners. As the dimensions get larger, the percentage of empty space grows smaller. But at certain dimensions, the packing uses all the space and these codes are the so-called perfect codes. There are very few of these codes.

Another property is the number of neighbors a single codeword may have.<a href="#cite_note-schlegel-1">[1]</a>

Again, consider pennies as an example. First we pack the pennies in a rectangular grid. Each penny will have 4 near neighbors (and 4 at the corners which are farther away). In a hexagon, each penny will have 6 near neighbors. Respectively, in three and four dimensions, the maximum packing is given by the <a href="12-face" class="mw-redirect" title="12-face">12-face</a> and <a href="24-cell" title="24-cell">24-cell</a> with 12 and 24 neighbors, respectively. When we increase the dimensions, the number of near neighbors increases very rapidly. In general, the value is given by the <a href="Kissing_number" title="Kissing number">kissing numbers</a>.

The result is that the number of ways for noise to make the receiver choose

a neighbor (hence an error) grows as well. This is a fundamental limitation

of block codes, and indeed all codes. It may be harder to cause an error to

a single neighbor, but the number of neighbors can be large enough so the

total error probability actually suffers.<a href="#cite_note-schlegel-1">[1]</a>

<ul><li><a href="Channel_capacity" title="Channel capacity">Channel capacity</a></li>

<li><a href="Shannon%E2%80%93Hartley_theorem" title="Shannon–Hartley theorem">Shannon–Hartley theorem</a></li>

<li><a href="Noisy_channel" class="mw-redirect" title="Noisy channel">Noisy channel</a></li>

<li><a href="List_decoding" title="List decoding">List decoding</a><a href="#cite_note-schlegel-1">[1]</a></li>

<li><a href="Sphere_packing" title="Sphere packing">Sphere packing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChristian_Schlegel_and_Lance_Pérez2004" class="citation book cs1">Christian Schlegel and Lance Pérez (2004). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=9wRCjfGAaEcC&pg=PA73">Trellis and turbo coding</a>. Wiley-IEEE. p. 73. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-22755-7</bdi>.</cite>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFJ.H._van_Lint1992" class="citation book cs1"><a href="Jack_van_Lint" class="mw-redirect" title="Jack van Lint">J.H. van Lint</a> (1992). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint/page/31">Introduction to Coding Theory</a>. <a href="Graduate_Texts_in_Mathematics" title="Graduate Texts in Mathematics">GTM</a>. Vol. 86 (2nd ed.). Springer-Verlag. p. <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint/page/31">31</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-54894-7</bdi>.</cite></li>

<li><cite id="CITEREFF.J._MacWilliamsN.J.A._Sloane1977" class="citation book cs1"><a href="Jessie_MacWilliams" title="Jessie MacWilliams">F.J. MacWilliams</a>; <a href="Neil_Sloane" title="Neil Sloane">N.J.A. Sloane</a> (1977). <a rel="nofollow" class="external text" href="https://archive.org/details/theoryoferrorcor0000macw">The Theory of Error-Correcting Codes</a>. North-Holland. p. <a rel="nofollow" class="external text" href="https://archive.org/details/theoryoferrorcor0000macw/page/35">35</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-85193-3</bdi>.</cite></li>

<li><cite id="CITEREFW._HuffmanV.Pless2003" class="citation book cs1">W. Huffman; <a href="Vera_Pless" title="Vera Pless">V.Pless</a> (2003). <a rel="nofollow" class="external text" href="https://archive.org/details/fundamentalsofer0000huff">Fundamentals of error-correcting codes</a>. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-78280-7</bdi>.</cite></li>

<li><cite id="CITEREFS._LinD._J._Jr._Costello1983" class="citation book cs1">S. Lin; D. J. Jr. Costello (1983). Error Control Coding: Fundamentals and Applications. Prentice-Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-283796-X</bdi>.</cite></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Charan Langton (2001) <a rel="nofollow" class="external text" href="http://complextoreal.com/wp-content/uploads/2013/01/block.pdf">Coding Concepts and Block Coding </a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-28" href="https://en.wikipedia.org/wiki/?title=Block_code&oldid=1282779815">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>